import java.util.ArrayList;


public class Ex6_3 {

	public Ex6_3() {
		result = "";
	}

	public String result;

	public static void main(String[] args) {

		Ex6_3 exer = new Ex6_3();
		ArrayList<String> inputs = Utils.readLines("C:\\Users\\josemfer\\Downloads\\dataset_74_5.txt");
		String v = inputs.get(0);
		String w = inputs.get(1);
		Integer[][] backt = exer.getBacktrack(v, w).get(0);
		exer.getOutputLCS(backt,v,v.length(),w.length());
		Utils.writeFile(exer.result, "C:\\Users\\josemfer\\Downloads\\out_6_3.txt");
		System.out.println(exer.result);

	}


	private void getOutputLCS(Integer[][] backtrack, 
			String v, Integer i, Integer j) {
		//System.out.println("i=" + i + "   j=" + j);
		if (i == 0 || j == 0) {
			return;
		}
		if (backtrack[i][j] == -1) {
			getOutputLCS(backtrack,v,i-1,j);
		} else if (backtrack[i][j] == 1) {
			getOutputLCS(backtrack,v,i,j-1);
		} else {
			getOutputLCS(backtrack,v,i-1,j-1);
			//System.out.print(v.charAt(i));
			result += v.charAt(i-1);
		}		
	}	

	private ArrayList<Integer[][]> getBacktrack(String v, String w) {	
		ArrayList<Integer[][]> results = null;			
		Integer n = v.length();
		Integer m = w.length();
		Integer s[][] = new Integer[n+1][m+1];
		Integer back[][] = new Integer[n+1][m+1];
		for (int i=0;i<=n;i++) {
			s[i][0] = 0;
		}
		for (int j=0;j<=m;j++) {
			s[0][j] = 0;
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=m;j++) {
				Integer down = s[i-1][j];
				Integer right = s[i][j-1];
				Integer diag = 0;
				if (v.charAt(i-1) == w.charAt(j-1)) {
					diag += s[i-1][j-1]  + 1;
					back[i][j] = 0;
				}				
				s[i][j] = Utils.max(new Integer[]{down,right,diag});

				if (back[i][j] == null) {
					if (s[i][j] == s[i-1][j]) {
						back[i][j] =  -1;
					} else if (s[i][j] == s[i][j-1]) {
						back[i][j] = 1;
					} 
				}

			}				
		}
		results = new ArrayList<Integer[][]>();		
		results.add(back);
		results.add(s);		
		return results;
	}

}
